import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.removeDuplicates("abcabbacddba"));
    }

    public String removeDuplicates1(String s) {
        /**
         * 删除字符串中的所有相邻重复项
         * 算法逻辑：
         *  使用栈后进先出的特性，每次枚举到新值都可以通过栈观测到前一个元素，若是相同则出栈，不同则入栈，满足题意*/
        // 1 预处理
        int n = s.length();
        Stack<Character> stack = new Stack<>();

        // 2 执行逻辑
        for(int i = 0; i < n; i++) {
            if(!stack.isEmpty() && stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        // 3 返回值
        StringBuilder retStr = new StringBuilder();
        while(!stack.isEmpty()) {
            retStr.append(stack.pop());
        }
        return retStr.reverse().toString();
    }

    public String removeDuplicates(String s) {
        /**
         * 删除字符串中的所有相邻重复项
         * 解法2：
         *  由于本题较为简单，故我们甚至可以不用到栈，直接使用StringBuilder即可*/
        // 1 预处理
        int n = s.length();
        StringBuilder retStr = new StringBuilder();

        // 2 执行逻辑
        // -此处使用指针记录最后元素下标是一个比较好的选择，可以避免多次对retStr求length
        int endIndex = -1;
        for(int i = 0; i < n; i++) {
            if(endIndex >= 0 && retStr.charAt(endIndex) == s.charAt(i)) {
                retStr.deleteCharAt(endIndex);
                endIndex --;
            } else {
                retStr.append(s.charAt(i));
                endIndex ++;
            }
        }

        // 3 返回值
        return retStr.toString();
    }
}
